class Solution:
    def uniquePathsIII(self, grid: list) -> int:
        def move(grid, i, j):
            top = (i - 1, j) if i - 1 >= 0 else None
            down = (i + 1, j) if i + 1 < len(grid) else None
            left = (i, j - 1) if j - 1 >= 0 else None
            right = (i, j + 1) if j + 1 < len(grid[i]) else None

            return [top, down, left, right]

        def func(grid, i, j, visited, sumPath, path):
            if grid[i][j] == -1:
                return 0
            if grid[i][j] == 2:
                return 1 if sumPath == path else 0
            res = 0
            for dire in move(grid, i, j):
                if dire is None:
                    continue
                x, y = dire
                if visited[x][y]:
                    continue
                visited[x][y] = True
                res += func(grid, x, y, visited, sumPath, path + 1)
                visited[x][y] = False

            return res

        visited = [[False for _ in range(len(grid[0]))]
                   for _ in range(len(grid))]

        x = 0
        y = 0
        sumPath = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    x = i
                    y = j
                    visited[i][j] = True
                elif grid[i][j] == 0 or grid[i][j] == 2:
                    sumPath += 1
        return func(grid, x, y, visited, sumPath, 0)
